class Node {
    Object data;
    Node left;
    Node right;

    public Node() {
        this(null);
    }

    public Node(Object data) {
        this.data = data;
        left = null;
        right = null;
    }
}

interface TreeDataCmp {
    int cmp(Object d1, Object d2);
}

public class Tree {
    Node root;
    TreeDataCmp cmpObj;
    int len = 0;

    public Tree() {
        root = null;
        cmpObj = null;
    }

    public Tree(TreeDataCmp cmpObj) {
        root = null;
        this.cmpObj = cmpObj;
    }

    public Tree setCmp(TreeDataCmp cmpObj) {
        this.cmpObj = cmpObj;
        return this;
    }

    public Tree add(Object addData) {
        Node newNode = new Node(addData);
        int ret;

        len++;

        if (root == null) {
            root = newNode;
        } else {
            Node tail = root;
            while (true) {
                ret = cmpObj.cmp(addData, tail.data);
                if (ret >= 0) {
                    if (tail.right == null) {
                        tail.right = newNode;
                        break;
                    }
                    tail = tail.right;
                } else if (ret < 0) {
                    if (tail.left == null) {
                        tail.left = newNode;
                        break;
                    }
                    tail = tail.left;
                }
            }
        }

        return this;
    }
    public Node findNode(Object key) {
        Node tail = root;
        while (true) {
            ret = cmpObj.cmp(key, tail.data);
            if (ret > 0) {
                if (tail.right == null) {
                    break;
                }
                tail = tail.right;
            } else if (ret < 0) {
                if (tail.left == null) {
                    break;
                }
                tail = tail.left;
            } else {
                return tail;
            }
        }

        return null;
    }

    public Object find(Object key) {
        Node tail = findNode(key);
        return (tail == null) ? null : tail.data;
    }

    public void fro(Node root) {
        if (root == null)
            return;
        System.out.print(root.data + " ");
        fro(root.left);
        fro(root.right);
    }

    public void mid(Node root) {
        if (root == null)
            return;
        mid(root.left);
        System.out.print(root.data + " ");
        mid(root.right);
    }

    public void end(Node root) {
        if (root == null)
            return;
        end(root.left);
        end(root.right);
        System.out.print(root.data + " ");
    }

    public void level(Node root) {
        Node [] queue = new Node[len];
        int front = 0;
        int end = 0;

        queue[end++] = root;

        while (front != end) {
            root = queue[front++];
            System.out.print(root.data + " ");
            if (root.left != null)
                queue[end++] = root.left;
            if (root.right != null)
                queue[end++] = root.right;
        }
    }

    public Tree travel(int flag, String prompt, Object ... obj) {
        System.out.printf(prompt, obj);
        switch (flag) {
            case 0:
                level(root);
                break;
            case 1:
                fro(root);
                break;
            case 2:
                mid(root);
                break;
            case 3:
                end(root);
                break;
            default:
                break;
        }

        System.out.println();

        return this;
    }
}


